/**
 * @author LKQ
 * @date 2022/2/28 14:49
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5,
                new ListNode(6, new ListNode(7)))))));
        Solution solution = new Solution();
        solution.oddEvenList(head);
    }
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        // 连接索引为奇数的点
        ListNode p = head;
        // 连接索引为偶数的点
        ListNode q = head.next;
        ListNode ou = new ListNode(0, q);
        while (q != null && p.next != null && q.next != null) {
            p.next = p.next.next;
            q.next = q.next.next;
            p = p.next;
            q = q.next;
        }
        // p指向奇数的最后一个，ou.next指向 q, 偶数的第一个， 将奇数链和偶数链相连
        p.next = ou.next;
        return head;
    }
}
